package twobranchTree.inorderTraversal;

import java.util.ArrayList;
import java.util.List;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/2/10
 * @author 王光浩
 * @Description 给出一棵二叉树，对它进行中序遍历。
 * @Method 使用递归方法进行
 *         d复杂度分析：时间复杂度O（n），空间复杂度O（n）
 */
public class MyMethodOne {
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<Integer>();
		if (root != null)
			inorder(root, result);
		return result;
	}

	/**
	 * @param node the root node
	 * @param result save the value
	 */
	private void inorder(TreeNode node, List<Integer> result) {
		if (node.left != null)
			inorder(node.left, result);
		result.add(node.val);
		if (node.right != null)
			inorder(node.right, result);
	}
	
	private List<Integer> ret = new ArrayList<Integer>();
	public List<Integer> inorderTraversal2(TreeNode root) {
		if (root == null)
			return ret;
		if (root.left != null)
			inorderTraversal2(root.left);
		ret.add(root.val);
		if (root.right != null)
			inorderTraversal2(root.right);
		return ret;
	}
}
